package net.flintx.array;

public class MinCostClimbingStairs {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }

    public static void main(String[] args) {
    }
}

// cost[] = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
// dp[0] = cost[0] = 1
// dp[1] = cost[1] = 100
// dp[2] = min(dp[0], dp[1]) + cost[2] = 2
// dp[3] = min(dp[1], dp[2]) + cost[3] = 3
// `dp[i]` 表示使用第i层后登顶的最小花费，那么明显 `dp[i] = min(dp[i-1], dp[i-2]) + cost[i]`
// 答案就是 `min(dp[cost.length-1], dp[cost.length-2])`